The continued proliferation of cloud computing platforms that enable the building, hosting, and scaling of applications and user-provided services on large-scale compute clusters has led to an increase in systems and methods for managing these platforms. One of the functions of the cloud operating system is to decide, when a new application is deployed, onto which machines the instances constituting this application should be allocated. This decision is governed by different constraints, and has implications on the performance, scalability, and fault-tolerance of the service. One consideration is that the allocation of instances to machines creates machine update constraints, i.e., which machines can or cannot be rebooted at the same time.